package dynamicProgramming

// 剪绳子
// 一段长度为n的绳子，请把绳子剪成m段（m和n都是整数，都大于1），
// 每段绳子长度相乘的最大乘积是多少
// 如当绳子长度为8时，我们剪成2 3 3 这三段，此时得到的乘积最大

func MaxProductAfter(length int) int {
	if length < 2 {
		return 0
	}
	if length == 2 {
		return 1
	}
	if length == 3 {
		return 2
	}

	products := make([]int, length+1)
	products[0] = 0
	products[1] = 1
	products[2] = 2
	products[3] = 3

	var max = 0
	for i := 4; i <= length; i++ {
		max = 0
		for j := 1; j <= i/2; j++ {
			product := products[j] * products[i-j]
			if max < product {
				max = product
			}
			products[i] = max
		}
	}

	return products[length]
}
